q21ubfandomcom-20200214-history
How can I trust a digital transaction made using Bitcoins?
=A Short Answer= ---- Commerce is the exchange of goods and services from the point of production to the point of consumption to satisfy human wants. ''When we talk about commerce we mean the whole system of an economy that constitutes an environment for business, where business refers to those activities engaged by an organization for increase its profit. Commerce is made of companies that try to maximize their profits by offering products and services to the market (made of both individuals and other companies) at the lowest production cost. When all those activities are conducted over an electronic system, such as Internet, we call it Electronic Commerce, or better known as e-Commerce. The origins of commerce is dated back to the very start of interaction between individuals in prehistoric times. Prehistoric people bartered what they had for goods and services with each other. Later, the introduction of currency as a standardized money facilitated a wider exchange of goods and services, overcoming the major bartering disadvantage, known as the [http://en.wikipedia.org/wiki/Coincidence_of_wants ''double coincidence of wants]. In fact, the main difficulty in barter is to find two persons whose disposable possessions mutually suit each other's wants. For example, if a man who makes pots for living needs a new house, he may wish to hire someone to build it for him. But he cannot make an equivalent number of pots to equal this service done for him, because even the builder might not want the pots. Currency used as a common unit solved this problem. We can assign values in currency unit to goods and services and thus collect and store them for later use. In our example, using a currency system, the man who makes pots can produce and sell several pots to different customers, such that he will collected the required money for paying the house builder. The first monetary system to be adopted is the the so called commodity, o representative, system. In the representative system a commodity such as gold, or silver, is made the unit of value and physically used as money for exchanges. Any other form of money, such as paper notes, are available but it has to be theoretically always possible to convert them into gold. Today the commodity money system has been replaced by a fiat money system in which money is paper currency or base metal coinage and its value is defined by a central bank and government law, or fiat (from latin let it be done). Fiat money can also be bank money, i.e., simply data records, such as bank balances and records of credit or debit card purchases. Any monetary system is based on trust. We have to trust the central bank to not debase the currency. We entrust our currency to a bank that promises to store and protect out notes. We also trust them with our privacy. Whenever we want to exchange money not in person we need a trusted third party that certifies and processes the exchange. The needs of trust becomes even more urgent when we start trading using any form E-commerce. In fact, e-commerce always requires financial institutions to act as trusted third parties when processing payments. While this trusted third party system works well for processing the transactions, it still suffers from the general and inherent weaknesses of the trust based model: in a trust based model financial authorities cannot avoid mediating disputes, thus making the transaction reversible. The cost of the mediation increases transaction costs, that is translated in chargebacks for the merchants that are forced to raise prices. Also the minimum practical transaction size is limited from the minimum transaction cost. Reversible transactions also require users to disclose more information about their identity, giving them very little privacy. All this problems can be avoided by trading in person using a physical currency, but no mechanism exists using traditional currency to make payments over a communications channel without a trusted third party. The real solution at this problem is to replace the trust based model with model in which the electronic payment is verified through a cryptographic proof. In this way two trading parties can exchange currency directly without need of trusted third party. If transactions are made computationally impractical to be reversed, the seller will be automatically protected from fraud, e.g. being payed with non-existing money, and the problem of double spending', i.e., using twice the same amount of money, is also avoided. '' Bitcoin This solution exists and it is called Bitcoin. Bitcoin (BTC), is a decentralized digital currency based on an open-source, peer-to-peer internet protocol and it was introduced in 2008 by a pseudonymous developer named Satoshi Nakamoto . Today, Bitcoin is the most widely used alternative currency and already a few hundreds of companies and individuals are accepting Bitcoin as a form of payment. Since mid 2010, the exchange rate of Bitcoin rose from some US cent up to a first peak of 30 USD in mid 2011. After a deep fall occurred due to obscure security leakage episodes, the exchange rate rose again form 5 USD up to another record peak of almost 250 USD in April 11th '13. At the time of writing, April 18th '13, the exchange rate has dropped down to less than 100 USD. In the figure to the right the exchange rate curve is shown form time-zero to April 18th '13. As of April 18th 2013, for the Bitcoin currency the monetary base, the part of the money supply which is highly liquid, e.g., notes, coins, commercial bank deposits with the Central Bank, is valued at over 1.07 billion of USD, but in April 11th a incredible peak was reached of about 2.6 billion of USD. In figure to left the monetary base is shown form time-zero to April 18th '13. In other words, Bitcoin is the first widely-adopted online currency that does not require the use of financial institutions to conduct transactions. However, the great attention given to the virtual currency from media in the last months, mostly due to to the mini-bank run in Cyprus, lead Bitcoin to be considered a new economic bubble, as the well-known Tulip Mania (15th century), dot-com (2001), and house pricing (2008) among others. As today, April '13, the exchange rate is dramatically dropped, sign that the bubble has burst. Nevertheless, there are still people who believe in it and willing to trade in it, and more important, there are still people using Bitcoin for its original purpose, being a well-designed and efficient decentralized means of exchange. How does it work? In the Bitcoin system electronic payments are performed through transactions that transfer bitcoins between a payer and a payee. These two entities, also know as peers, are anonymously addressed by means of Bitcoin addresses, that is totally independent from the peer real identity (e.g. name, ID numbers), real location (e.g. home addreses) and virtual location (e.g. IP address). Addresses are stored in the digital wallet of the peer, and each wallet can contain different addresses. Moreover each address have an associated pair of public and private keys. Bitcoin uses public key cryptography to digitally sign and verify each transaction. With a public key cryptography we need two different keys, a public key and private key, in oder to encrypt and decrypt messages. These two keys are related through mathematical functions, but at the same time they are totally different and it is extremely difficult for anyone to derive the private key, based only on the knowledge of the public key. The private key is used to lock or encrypt some information, while the public key is used to unlock or decrypt the same information. Neither key can perform both functions by itself. The public key may be published without compromising security, while the private key must not be revealed to anyone unauthorized to read the messages. In Bitcoin the payer signs the transaction with its private key, and anybody can validate the signature using the payer public key. Whenever a payer has to transfer coins to the payee, the former will digitally sign, using its private key, the hash of the previous transaction (or transactions) and the public key of the payee. An hash is a short representation of a longer data set obtained through a specific hash function. In this way the new transaction will contain the compressed information about all the previous transaction from which those exchanged coins come from. In the figure on the right the transaction creation is shown. A previous transaction is hashed together with the payee (Owner 1) public key from the payer (Owner 0) and then digitally signed using the payer private key. The same is repeated from Owner 1 and Owner 2, and finally the amount of money is owned by Owner 3. Every time a transaction is create, it is broadcasted in all the network and can be verified by all the peers. According to this scheme we have a form of digital distributed consensus between the (peer) nodes of a (p2p) network. Following, an example from the Bitcoin wiki is presented, assuming that Alice wants to send a Bitcoin to Bob we have: #Bob sends his address (from which the public key can be derived) to Alice. #Alice adds Bob’s public key and the amount of bitcoins to transfer to a message: a ''transaction message. #Alice signs the transaction with her private key. #Alice broadcasts the transaction on the Bitcoin network for all to see. Looking at this transaction from the outside, anyone who knows that these addresses belong to Alice and Bob can see that Alice has agreed to transfer the amount to Bob, because nobody else has Alice's private key. Assume now that that Bob wants to transfer the same bitcoins to Charley. Thus we have: #Charlie sends Bob his address. #Bob adds Charlie's public key and the amount of bitcoins to transfer to a message: a transaction message. #Bob signs the transaction with his private key. #Bob broadcasts the transaction on the Bitcoin network for all to see. Assume now that a forth user, Eve, wants to make Charlie believe that she actually owns Bob money. In order to do that, Eve should replace Bob’s public key, hashed in Alice transaction, with her own public key. Of course, this cannot be done, because Alice transaction is signed with Alice private key, that is kept secret from Eve. So Charlie can verify that originally the coins were in Alice's wallet, then from Alice to Bob, and finally from Bob to him. It is important to understand that the transaction can be created starting from one or more previous transactions, such that the received coins can be easily split and combined. For example, we have a single input transaction from a larger previous transaction or multiple inputs combining smaller amounts. In this sense, if Bob want to send to Charlie more Bitcoins than those received from Alice, it can hash Alice transaction with any other previously received transaction such that he reaches the desired amount of coins. Now, what happen if Alice try to use the same coins transferred to Bob for a new transaction? Is the system described robust enough to prevent the so called double spending problem? =A Long Answer= ---- In the short answer we presented the basic functionality of Bitcoin. We understood how Bitcoin protects transactions by allowing the payer and the payee to verify the payment without using any trusted third party, but simply relaying on public and private key cryptography. However there is another important problem that needs to be addressed, the double spending attack. Double spending attack The double spending attack takes place when a payer attempts to use the same coins for more than one payment. Unfortunately, this cannot be verified by the payee with the cryptography tools presented so far. A tradition solution to this problem is to introduce a central authority that is aware of all transactions and can check for double spending. However, this represents an undesired solution for a distributed virtual currency, thus is necessary to find a solution that do not involve any trusted party. For this purpose, in Bitcoin all the transactions are publicly announced and a robust timestamp system makes every node of the network agreed on a unique transactions history, such that the payee can verify that each transaction is not duplicated in time. As already mentioned, the solution proposed in Bitcoin is based on a timestamp approach -- transactions are hashed using a particular hash function, and the hash is widely published. Since data must have existed at the time of publishing in order to be hashed, publishing the hash means timestamping the data. Moreover each new timestamp includes inside the previous timestamps in its hash, thus to form a chain. The problem with solution is the following. How to implement a timestamp system in a distributed fashion such that an attacker node cannot compromise the transactions stored in the network? Bitcoin uses a proof-of-work (PoW) system. Briefly, to hash transactions, a Bitcoin node must find a nonce, an arbitrary number for the nonce (occasion), that, when hashed with the transactions, the resulting hash begins with a specific number of zero bits. The average work required to find the nonce is exponential in the number of zero bits required and can be verified by executing a single hash. The hashed transactions form a block together with the hash of a previous block created similarly by some other node the network. The result is a chain of blocks. More specifically, this is what happens: #Every new transaction is broadcast in the network. New transaction broadcasts do not necessarily need to reach all nodes. As long as they reach many nodes, they will get into a block soon. #Each node collects new transactions and verifies that they are correct in format and the coins used are not double-spent. If a transaction satisfies these request, it is temporarily stored in memory. #Each node works on finding a difficult proof-of-work for constructing a block of transactions. When a node finds a proof-of-work, i.e., it find the nonce, it hashes the transaction stored in memory, creates a block and broadcasts the block to all nodes. New block broadcasts need to reach all nodes. If a node does not receive a block, it will request this as soon as it receives the subsequent block and realizes that one is missing. #Other nodes consider the block valid only if the hash of the block is valid and all transactions contained in it are correct and not already spent. #If the received block is accepted by a node, this will starts creating a new block to concatenate at the same chain. With this PoW system if a peer wants to double-spend a coin he needs to change the information of the transaction in which the coin was previously spent, and consequently redo the PoW for the block in which the transaction was hashed. Otherwise, the double-spending would be immediately detected by any peer in the network, since every node in the network maintains the chains of block, thus the history of all the transactions. But there is more. Since the blocks are chained together, a malicious peer needs to repeats the PoW not only for the block containing the transaction of interest, but also all the other blocks following in the chain. According to this, the double-spending problem is no feasible as long as the number of honest peers in the network is greater than the number of colluding peers. In fact the transaction is verified by the majority, and this majority is based on a one-CPU-one-vote system. The majority decision is represented by the longest chain of blocks circulating in the network, that correspond to the one with the greatest proof-of-work effort invested in it. If a majority of CPU power in the network is controlled by honest nodes, the honest chain will grow faster than any other chain. If a attacker wants to modify a past block he needs to redo the proof-of-work of the block and all blocks after it in the chain with a pace that allows him to catch up with and surpass the work of the honest nodes. Clearly, the one-CPU-one-vote system outperform in terms of security level a simple one-IP-address-one-vote system. With one-IP-address-one-vote system, the majority decision can be affected by anyone able to allocate many IP addresses, while a one-CPU-one-vote system together with a PoW make the fraud hard to be accomplished. In the following example we evaluate the scenario of an malicious node trying to generate an alternate chain longer, and generated faster, than the honest chain in order to perform a double-spending attack. Example: The Gambler's ruin problem In this example we consider an attacker willing to generate an alternate chain that grown faster than the honest chain such to become bigger and thus being accepted in the network as current chain. It is important to capitalize that even if the attacker succeed in his intent he will be able to change only the information about his old transaction, that is generating a double-spending attack. However, he will not be able to create new coins or appropriate of other's coins, since all the honest nodes will never accepts such fraudulent transactions. The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The idea behind is simple. Imagine you are walking along a line, and the step size is constant. Before each step, you flip an unbiased coin, such that the probability of heads or tails are equal. If the coin gives you heads, you go one step forward, otherwise you go one step back. In Bitcoin this can be reinterpreted as a success event, an head, is the honest chain being extended by one block, increasing its length by +1, while and the failure event, a tail, is the attacker's chain being extended by one block, reducing the gap by -1. If the starting position of our walk is the distance from the attacker, we are interested in estimating the probability of an attacker catching up starting from a given deficit, i.e., distances in terms of block in the two chains. Another way to describe this problem is using the Gambler's ruin analogy. Consider a gambler player who wins or loses a dollar with probabilities p'' and ''q, respectively. Let his initial capital be z'' and let him play against an adversary with initial capital ''(a-z), so that the combined capital is a''. The game continues until the gambler's capital either is reduced to zero or has increased to ''a, that is, until one of the two players is ruined. We are interested in the probability of the gambler's ruin. Let qz be the probability of the gambler's to lose the game and pz the probability of his winning the game. After the first trial the gambler's fortune can be (z-1) if loose or (z+1) if win. Using the theorem of the total probability we have: q_z = pq_{z+1}+qq_{z-1}, \ \ \ \ \ \ \ \ \ \ (1) that is, the probability of loosing starting from z'' is equal to the probability of loosing starting form ''(z+1) if we win (time that probability of winning) plus the probability of loosing starting form (z-1) if we loose (time the probability of loosing). When z=1, the first trial may lead the player to ruin, thus Eq. (1) becomes q1 = pq2+q, when z=a-1, the first trial may lead the player to win, thus Eq. (1) becomes qa-1 = qqa-2. We obtain q0=1, if we start with zero we loos with probability one, and qa=0, since for z=a the player has already won. The result is a second order difference equation with boundary conditions on qz. To solve the second order equation we look for solution of Eq. (1) in the form of the generic solution of a first order equation, qn=xz. If we substitute the solution in the equation we obtain the so called characteristic polynomial: px^2-x+q=0, \ \ \ \ \ \ \ \ \ \ (2) with roots in x=1 and x=\frac{q}{p} , that represent two particular solutions of Eq. (1), q_z=1 and q_z=\left(\frac{q}{p}\right)^z . The general solution can be written as q_z= A+B\left(\frac{q}{p}\right)^z, \ \ \ \ \ \ \ \ \ \ (3) where A and B are arbitrary constants that can be determined by using the border conditions. We get A + B = 1 and A+B\left(\frac{q}{p}\right)^z=0 that gives: q_z = \frac{\left(\frac{q}{p}\right)^a-\left(\frac{q}{p}\right)^z}{\left(\frac{q}{p}\right)^a-1}. \ \ \ \ \ \ \ \ \ \ (4) Now that we obtained this result, we can see how it helps with our original problem, finding the probability of a malicious node to be able to create a chain of blocks longer than the one created by honest nodes. Here the gambler player becomes the attacker, z'' represents the difference in terms of blocks between the attacker chain and the honest chain. The objective of the attacker is to bring the distance to zero. The result found in (4) is still valid in this scenario, with the only difference that the distance is not upper limited, that means in the gambler problem playing against an infinity rich adversary. Therefore, for a\rightarrow \infty we have: q_z = \begin{cases} 1 & q>p\\ \left(\frac{q}{p}\right)^z & q Given our assumption that ''qTransactions and Blocks hashing Now that we discussed how the system is designed to allow users to make safe transactions and to avoid double spending fraud, it is important to understand from the technical point of view this security operation are performed. In particular we present here how the transactions and blocks containing groups of transactions are hashed. Merkle trees As we discussed above, every time users exchange Bitcoins they generate transactions. These transactions are broadcasted in the network and stored inside blocks in the chain of block shared by the all nodes in the network. The number of transactions per block is variable, and transactions are simply stored in the payload of the block, as we will discuss later on. Nevertheless, an iterative hashing operation is performed on these transactions before the block can be generated, and this lead to a Merkle tree creation, Merkle trees are binary trees of hashes. In particular a Merkle tree is a tree in which every non-leaf node, i.e., node that have other nodes in the lower level, is labelled with the hash of the labels of its children nodes. Using this hashes structure it is computational easy to verify the content of a large amount of data. In fact, to find is a leaf-node belong to an hash (balanced) tree we need to have an amount of data proportional to the log of the number of nodes in the tree, differently in a list tree the amount of data is directly proportional to the number of nodes. If each non-leaf node can have at most two children in the next lower level, the tree is a binary Merkle tree. In the figure to the right an example of binary Merkle tree is shown. The four data structures are hashed, and the hashes of the hashes are again hashed in order to obtain the top hash, also known as Merkle root. In Bitcoin Merkle trees use a double SHA-256 hashing function. SHA256, that belong to the set of cryptographic hash functions SHA-2 (Secure Hash Algorithm version 2). This set was designed by the National Security Agency (NSA) and published in 2001 as a U.S. Federal Information Processing Standard and consists of a set of four hash functions with output that are 224, 256, 384 or 512 bits. SHA256 has an output of 256 bits. Using a double SHA-256 means that each non-leaf node consist of the SHA-256 hash of the SHA-256 hash of something. For the bottom level of the tree, the transactions are double hashed (the leaves), while for the other levels of the tree is the ashes of the next level children to be double hashed. The procedure start from the bottom level of the tree where the byte streams of the transactions to be included in block are double-SHA-256 hashes. This create the upper level with the hashes of the transactions. These hashes are concatenated two by two and the concatenation is again double-SHA-256 hashed, creating another upper level of the tree. This procedure repeats recursively until we get a level with only one node. The hash corresponding to this node is the so called Merkle root of the tree. Whenever a level presents an odd number of elements, the last element is duplicated such that there is always an even number of element in each level. Following we shown an example using pseudo code about how to create a Merkle tree starting from an odd number of transactions. We define sha256(⋅) the hash operation based on SHA-256, and we also define d_sha256(⋅) = sha256(sha256(⋅)). The objective is to create he Merkle root of three transactions, ''t1, t2 and t3. The first step see the double-hash of the transaction. Since the number of transactions is odd, we pad the last position repeating the last transaction, t3. \mathrm where the symbol +'' represent the concatenation operation. Finally the Merkle root ''h_r is obtained by hashing together the last two hashes left: \mathrm The Merkle root, as we will seen in the next subsection becomes part of the block header. This complex operation is important because allows to reduce the disk space required to store the whole chain of blocks that keep increasing in size day by day. When an old transaction is buried under enough blocks, it would be desired to discard it in order to save disk space. This can be done since only the Merke roor is part of the header block that is hashed to create a new block, as we will see soon. The transaction are not hashed, and are in some sense included inside the Merkle root. In this way, for old blocks only the header need to be stored, that is only 80 bytes. Blocks hashing As mentioned before time, a block is a data structure, consisting of a header and a payload, that contains a group of transactions, plus other additional information such a timestamp and the hash of the previous block in chain among others. The transaction are contained in the block payload, while the header contains all the additional information. The block header structured is shown in Table below. In order to create the block the node keep hashing only the header of the block, until he find a nonce that gives the number of zero-bits target. The payload is not hashed, but the transaction are indirectly hashed because is the Merkle root to be hashed as we discussed in the previous subsection. For this reason, is easy to see that the hashing effort is independent from the number of transaction contained in it. The value of the header are not fixed, in particular we have: *Version. This number changes whenever the software is updated. *hashPrevBlock. This value changes if a new block is added in the chain from some other node in the network. *hashMerkleRoot. If a new transaction is accepted and stored in memory, this will be included in the same block. Therefore, this value will be updated. *Time. This value is updated every few seconds. *Bits. The target changes to adjust the difficulty of finding a nonce. The difficulty is adjusted every 2016 blocks based on the time it took to create them, i.e. to find the nonces. The desired rate is fixed to 10 min/block, that is 2016 blocks per two weeks. If the previous 2016 blocks were created in (less) more than two weeks the difficulty is (increased) reduced. *Nonce. This number starts from zero and is incremented every attempt to hash the header.